BFS—Worked Code Example - Educational Content

Run a full BFS on our 6-node graph, then use the results to reconstruct the path from node 'A' to 'E'.

This example shows a complete workflow: running BFS, then using its output to solve a problem.
First, we define the graph `G` as an adjacency list in a Python dictionary.
The conceptual `bfs(G, 'A')` function computes the `parent` and `level` maps for the entire graph starting from 'A'.
A helper function `path` is defined to reconstruct the path by backtracking from a target `t` to the source `s` using the `parent` map.
Finally, we print both the shortest path distance (`level['E']`) and the actual path from 'A' to 'E'.

Python Code Example

# Assume bfs(G, s) is defined from the previous slide
G = {
    'A': ['B', 'C'], 'B': ['A', 'D', 'F'], 'C': ['A', 'E'],
    'D': ['B', 'E'], 'E': ['C', 'D', 'F'], 'F': ['B', 'E']
}
parent, level = bfs(G, 'A')
def path(parent, s, t):
    if parent[t] is None and s != t: return None
    out, x = [], t
    while x is not None:
        out.append(x)
        x = parent[x]
    return list(reversed(out))
print(level['E'], path(parent, 'A', 'E'))